1989E - Distance to Different - CodeForces Solution

import sys
import math

class Solution:
    def solve(self, n, k):
        mod = 998244353
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        sum_dp = [0] * (k + 1)
        sum_dp[0] = 1
        
        for i in range(1, n + 1):
            for j in range(k, -1, -1):
                nj = min(j + 1, k)
                dp[i][nj] += sum_dp[j]
                if i > 2 and i != n:
                    dp[i][nj] -= dp[i - 2][j]
                dp[i][nj] %= mod
            
            for j in range(k + 1):
                sum_dp[j] += dp[i][j]
                sum_dp[j] %= mod
        
        return (dp[n][k] % mod + mod) % mod

input = sys.stdin.read().strip().split()
n = int(input[0])
k = int(input[1])

solution = Solution()
result = solution.solve(n, k)
print(result)